package com.since.algorithm.recursive;

/**
 * Created by Sincerity on 2020/5/11.
 * 描述：递归算法
 * 1. 小球找路系列{@link #findWay(int[][], int, int)}
 * 2. 阶乘问题 {@link #factorialResult(int)}
 * 3. 反阶乘求数 {@link #resultFa(int)}
 */
class BallFindWay {
    private static int i = 0;

    public static void main(String[] args) {
        int[][] map = new int[8][7];
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < 8; i++) {

            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        map[3][4] = 1;
        map[3][5] = 1;
        map[4][1] = 1;
        map[4][2] = 1;
        map[4][4] = 1;
        map[4][5] = 1;
        map[6][4] = 1;
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
        boolean way = findWay(map, 1, 1);
        System.out.print("是否找到出路=" + way + "\n");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("最终走过的" + i + "步数");

        System.out.printf("%d的反阶乘阶乘是%d\n", 479001600, resultFa(479001600));
//        System.out.printf("%d的阶乘是%d\n", 10, factorialResult(10));
    }

    private static int result = 1;
    private static int n = 0;

    /**
     * 阶乘算法
     *
     * @param num 一个数
     * @return 这个数的阶乘
     */
    private static int factorialResult(int num) {
        if (num > 1) {
            result *= num;
            factorialResult(--num);
        }
        return result;
    }

    /**
     * 反阶乘算法
     *
     * @param sum 知道某个数字 求它是最接近谁的阶乘
     * @return 这个数
     */
    private static int resultFa(int sum) {
        n += 1;
        result = 1;
        int value = factorialResult(n);
        if (value < sum) {
            resultFa(479001600);
        }

        return n;
    }

    /**
     * 根据地图找出路 下->右->上->左
     *
     * @param map   地图
     * @param statX x
     * @param statY y
     * @return 是否找到出路
     */
    private static boolean findWay(int[][] map, int statX, int statY) {
        i += 1;
        if (map[6][5] == 2) {
            return true;
        } else {
            System.out.format("当前第%d步 坐标 %d %d \n", i, statX, statY);
            if (map[statX][statY] == 0) { //表示没有走过
                map[statX][statY] = 2;
                //下->右->上->左
                if (findWay(map, statX + 1, statY)) {//下
                    return true;
                } else if (findWay(map, statX, statY + 1)) {//右
                    return true;
                } else if (findWay(map, statX - 1, statY)) {//上
                    return true;
                } else if (findWay(map, statX, statY - 1)) {//左
                    return true;
                } else { //死路
                    map[statX][statY] = 3;
                }
            } else { //1 墙壁 2 已经走过 3 出错
                return false;
            }
        }
        return false;
    }
}
